package leetcode32

func trapV2(height []int) int {
	var res int
	length := len(height)
	if length <= 2 {
		return 0
	}
	var leftMax []int = make([]int, length)
	var rightMax []int = make([]int, length)
	leftMax[0] = height[0]
	rightMax[length-1] = height[length-1]

	for i := 1; i < length; i++ {
		leftMax[i] = maxInt(height[i], leftMax[i-1])
	}

	for i := length - 2; i > 0; i-- {
		rightMax[i] = maxInt(height[i], rightMax[i+1])
	}

	for i := 1; i < length-1; i++ {
		res += minInt(leftMax[i], rightMax[i]) - height[i]
	}

	return res
}

func maxInt(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

func minInt(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

func trap(height []int) int {
	var res int

	length := len(height)

	for i := 1; i < length; i++ {
		var (
			leftMax  = 0
			rightMax = 0
		)
		for j := i; j >= 0; j-- {
			leftMax = maxInt(height[j], leftMax)
		}

		for k := i; k < length; k++ {
			rightMax = maxInt(height[k], rightMax)
		}
		res += minInt(leftMax, rightMax) - height[i]
	}
	return res
}
